package week_01;

public class ReverseNodesInKGroup_25_2 {

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode protect = new ListNode(0, head);
        ListNode last = protect;
        while (head != null) {
            ListNode end = getEnd(head, k);
            if (end == null) break;
            ListNode nextGroup = end.next;
            reverse(head, end);
            head.next = nextGroup;
            last.next = end;

            last = head;
            head = nextGroup;
        }

        return protect.next;
    }

    private ListNode getEnd(ListNode head, int k) {
        while (head != null) {
            k--;
            if (k == 0) break;//说明node数够k个
            head = head.next;
        }
        return head;// 如果node数不够k则会返回null
    }

    public void reverse(ListNode head, ListNode end) {
        if (head == end || head == null) return;
        // head 和 end 之间反过来
        ListNode last = head;
        head = head.next;
        while (head != end) {
            ListNode next = head.next;
            head.next = last;
            last = head;
            head = next;
        }
        // 手动补一次 最后一条边
        end.next = last;
    }

    public static void main(String[] args) {
        ReverseNodesInKGroup_25_2 solution = new ReverseNodesInKGroup_25_2();
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
        ListNode root = buildListNode(arr);
        printList(root);
        ListNode node = solution.reverseKGroup(root, 3);
        printList(node);
    }

    private static void printList(ListNode root) {
        while (root != null) {
            System.out.print(root.val + "->");
            root = root.next;
        }
        System.out.println();
    }

    private static ListNode buildListNode(int[] arr) {
        ListNode head = new ListNode();
        ListNode tail = head;
        for (int i = 0; i < arr.length; i++) {
            ListNode node = new ListNode();
            node.val = arr[i];
            tail.next = node;
            tail = tail.next;
        }
        return head.next;
    }
}
